package com.bupt.dp;
/**
 * 背包问题
 * @author feng
 *
 */
public class PackageProblems {
	/**
	 * 
	 * 题目描述： 有N件物品和一个容量为V的背包。第i件物品的费用是w[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大。
	 * 状态：dp[i][j]表示前i件物品，放入总背包重量为j的包中可达到的最大价值
	 * 状态转移方程：dp[i][j] = max{dp[i-1][j],dp[i-1][j-w[i]]+v[i]}
	 * 空间复杂度为N2的解法（未优化）
	 * @param w int型数组，重量数组
	 * @param v int型数组，价值数组
	 * @param C int类型，背包重量
	 * @return int 最大价值
	 */
	public int packageProblemI_1(int w[],int v[],int C){
		int len = w.length;
		int[][] dp = new int[w.length+1][C+1];
		//初始化
		for(int j = 1;j<=C;j++){
			dp[0][j] = Integer.MIN_VALUE;
		}
		for(int i = 1 ;i <= w.length;i++){
			for(int j = 0;j<=C;j++){
				//动态方程
				dp[i][j] = Math.max(dp[i-1][j],j>= w[i-1]?dp[i-1][j-w[i-1]]+v[i-1]:0);
			}
		}
		return dp[len][C];
	}
	/**
	 * packageProblemI_1  算法空间复杂度由N2优化为N
	 * @param w
	 * @param v
	 * @param C
	 * @return
	 */
	public int packProblemI_2(int w[],int v[],int C){
		return 0;
	}
}
